[리트코드]]_17.Letter Combinations of a Phone Number

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        R, C = len(grid), len(grid) and len(grid[0])
        cnt = 0
        visited = collections.defaultdict(bool)

        for i in range(R):
            for j in range(C):
                if grid[i][j] == '1' and not visited[(i, j)]:
                    cnt += 1
                    visited[(i, j)] = True
                    Q = deque()
                    Q.append((i, j))
                    while Q:
                        y, x = Q.popleft()
                        for dy, dx in [(1, 0), (-1, 0), (0, -1), (0, 1)]:
                            y2 = y + dy
                            x2 = x + dx
                            if y2 < 0 or y2 >= R or x2 < 0 or x2 >= C:
                                continue
                            if grid[y2][x2] != '1':
                                continue
                            if visited[(y2, x2)]:
                                continue
                            visited[(y2, x2)] = True
                            Q.append((y2, x2))

        return cnt

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
		def dfs(i, j):
            if i < 0 or i >= len(grid) or \
            j < 0 or j >= len(grid[0]) or \
            grid[i][j] != '1':
                return

            grid[i][j] = '0'
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)

        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    dfs(i, j)
                    count += 1

        return count